package heap;

/**
 * topK 问题 三种方法
 * 全排序 当数据量很大时  效率很低
 * 维护最大k个  后面的和k[0] 比较
 *              大于就放到 k[0]处  然后二分找到位置 前面的整体移位
 *              小于就丢弃
 *              但是放进去导致整体 移位极为耗时  从而改用堆的思想
 * 可以结合下面两种   选堆最小的那个   k < len - k + 1 时 用  最大k个值小根堆  否则最小len - k + 1个值大根堆
 *  最大k个值小根堆 法    topk  个最大值  根最小  这也是本题解法
 *  最小len - k + 1个值大根堆法   len - k + 1 个最小值  根最大  最大的k - 1  个值被舍弃掉了
 */
public class 数组中的第K个最大元素_215 {
 static void main(String[] args) {
        数组中的第K个最大元素_215 a = new 数组中的第K个最大元素_215();
        int kthLargest = a.findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2);
        System.out.println(kthLargest);
    }


    public int findKthLargest(int[] nums, int k) {
        int [] topK = new int[k];
        System.arraycopy(nums, 0, topK, 0, k);
        MinHeap minHeap = new MinHeap(topK);
        for(int i = k; i< nums.length ; i++) {
            if(nums[i] > minHeap.getRoot()) {
                minHeap.setRoot(nums[i]);
            }
            for(int t : minHeap.heapData) {
                System.out.print(t);
            }
            System.out.println();
        }
        return minHeap.getRoot();
    }

}

/**
 * 小根堆实现代码
 * 小根堆 ： 父节点的值小于等于两个子节点的值的完全二叉树 （除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐）
 *https://blog.csdn.net/zhaohong_bo/article/details/90368401?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EsearchFromBaidu%7Edefault-2.pc_relevant_baidujshouduan&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EsearchFromBaidu%7Edefault-2.pc_relevant_baidujshouduan
 * 存储结构是数组
 * 重点方法
 *          建堆 buildHeap
 *          堆调整 heapify
 *          插入 setRoot (调整堆的树根)
 *          删除 delete
 *          取最小值getRoot
 */
class MinHeap{
    protected int[] heapData;

    public MinHeap(int[] heapData) {
        this.heapData = heapData;
        buildHeap();
    }

    private void buildHeap() {
        // 完全二叉树只有数组下标小于或等于 (data.length) / 2 - 1 的元素有孩子结点，遍历这些结点。
        for( int i = heapData.length/2 -1 ; i>=0; i --) {
            heapify(i);
        }
    }

    private void heapify(int i) {
        // 获取左右结点的数组下标
        // i == 0 的时候 这种求法是有问题的   left == -1 了
        int left = 2 * (i + 1 ) -1;
        int right = 2 * (i + 1 );

        int smallest = i;


        if(right < heapData.length && heapData[right] < heapData[smallest]) {
            smallest = right;
        }

        if(left >= 0 && left < heapData.length && heapData[left] < heapData[smallest]) {
            smallest = left;
        }

        if(smallest == i) return;
        // 交换最小的到根节点
        swap(smallest, i);
        // 比如根节点的根节点 是 9  根节点是 7  叶子是 1
        // 换了  9  和 1 之后 变成从上往下  1  9  7   此时还要换子树的  9 和 7
        // 参考 https://blog.csdn.net/Zj_boring/article/details/105157360?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EsearchFromBaidu%7Edefault-1.pc_relevant_baidujshouduan&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EsearchFromBaidu%7Edefault-1.pc_relevant_baidujshouduan
        heapify(smallest);
    }

    private void swap(int smallest, int i){
        int tmp = heapData[i];
        heapData[i] = heapData[smallest];
        heapData[smallest] = tmp;
    }

    public int getRoot() {
        return heapData[0];
    }

    public void setRoot(int root) {
        heapData[0] = root;
        // 重新从上往下递归的调整堆
        heapify(0);
    }

    public void delete(int idx) {
        // 最后的叶子节点放到 idx处  重新往下交换
        heapData[idx] = heapData[heapData.length - 1];
        heapData[heapData.length - 1] = 0;
        heapify(idx);
    }
}
